/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package evaluation.ged;

import evaluation.Graph;
import evaluation.Vertex;
import evaluation.Edge;
import evaluation.GraphShower;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.regex.Pattern;
import util.StringSimWrapper;


/**
 * using A* algorithm
 * @author phong
 */
public class GraphEditDistance {
    
    Graph Gs, Gd;
    
    Queue<EditPath> open;
    
    public GraphEditDistance(Graph Gs, Graph Gd) {
        this.Gs = Gs;
        this.Gd = Gd;
    }
    
    public EditPath getBestEditPath() {
        open = new PriorityQueue<EditPath>();
        
        // init
        Vertex vs = Gs.getVertices().iterator().next();
        
        EditPath emptyEpath = new EditPath(Gs, Gd);
        
        for (Vertex v : Gd.getVertices()) {
            if (v.getType() == vs.getType()) {                        
                if (vs.getType() == Vertex.TYPE_OPT && vs.getLabel().equals(v.getLabel()) || 
                        vs.getType() == Vertex.TYPE_PRED && StringSimWrapper.calSim(vs.getLabel(), v.getLabel()) > 0.8 ||
                        vs.getType() == Vertex.TYPE_LABEL || vs.getType() == Vertex.TYPE_REF) {
                    EditPath ep = emptyEpath.copy();
                    ep.addVertexSubstitution(new VertexSubstitution(vs, v));                            
                    open.offer(ep);
                }
            }
        }
        EditPath ep = emptyEpath.copy();
        ep.addVertexDeleteion(new VertexDeletion(vs));
        open.offer(ep);
        
        // loop until find the best edit path
        int i = 0;
        while (true) {
            EditPath epath = this.open.poll();

            System.out.println("--------------");
            System.out.println(i);
            System.out.println(epath.getCost());
            System.out.println(epath.getCost() + epath.getFutureCost());
            System.out.println(open.size());
            i++;
            
            if (epath.successful())
                return epath;
            
            Graph S = epath.getGs();
            Graph D = epath.getGd();
            
            // get an unmapped vertex in S
            // lex-vertex is preferred
            Set<Vertex> candidates = new LinkedHashSet<Vertex>(S.getVertices());
            candidates.removeAll(epath.getMappedVertices());
            
            // if there is at least one unmapped vertex in S
            if (!candidates.isEmpty()) {
                vs = candidates.iterator().next();

                // do edit operation
                candidates = new LinkedHashSet<Vertex>(D.getVertices());
                candidates.removeAll(epath.getMappedVertices());
                
                for (Vertex v : candidates) {
                    if (v.getType() == vs.getType()) {                        
                        if (vs.getType() == Vertex.TYPE_OPT && vs.getLabel().equals(v.getLabel()) || 
                                vs.getType() == Vertex.TYPE_PRED && StringSimWrapper.calSim(vs.getLabel(), v.getLabel()) > 0.8 ||
                                vs.getType() == Vertex.TYPE_LABEL || vs.getType() == Vertex.TYPE_REF) {
                            ep = epath.copy();
                            ep.addVertexSubstitution(new VertexSubstitution(vs, v));                            
                            open.offer(ep);
                        }
                    }
                }        
                
                ep = epath.copy();
                ep.addVertexDeleteion(new VertexDeletion(vs));
                open.offer(ep);
            }
            // if there is no unmapped vertex left in S
            else {
                candidates = new LinkedHashSet<Vertex>(D.getVertices());
                candidates.removeAll(epath.getMappedVertices());
                
                ep = epath.copy();
                for (Vertex v : candidates) {
                    ep.addVertexInsertion(new VertexInsertion(v));
                }
                open.offer(ep);
            }
        }
    }
    
    public static void main(String[] args) {
        
        Vertex a1 = new Vertex("a1", Vertex.TYPE_REF);
        Vertex a2 = new Vertex("a2", Vertex.TYPE_REF);
        Vertex p = new Vertex("p", Vertex.TYPE_PRED);
        
        Edge a1p = new Edge("", a1, p);
        
        Graph Gd = new Graph(
                new LinkedHashSet<Vertex>(Arrays.asList(new Vertex[]{a1, p})), 
                new LinkedHashSet<Edge>(Arrays.asList(new Edge[]{a1p})), 
                new LinkedList<Vertex>());
        Graph Gs = new Graph(
                new LinkedHashSet<Vertex>(Arrays.asList(new Vertex[]{a2})), 
                new LinkedHashSet<Edge>(Arrays.asList(new Edge[]{})), 
                new LinkedList<Vertex>());
        
        GraphEditDistance ged = new GraphEditDistance(Gs, Gd);
        EditPath ep = ged.getBestEditPath();
        System.out.println(ep);
        GraphShower.show(ep.Gs);
    }
}
